package com.tgy.algorithm._经典题目01;

public class _018_最长公共子串 {

    public static String maxSubArr(String one,String two) {

        if (one == null || one.length() == 0
                || two == null || two.length() == 0) {
            return null;
        }

        int oneLen = one.length();
        int twoLen = two.length();

        char[] oneChars = one.toCharArray();
        char[] twoChars = two.toCharArray();

        int[][] caches = new int[oneLen][twoLen];

        for (int i = 0; i < twoLen; i++) {
            caches[0][i] = oneChars[0] == twoChars[i] ? 1:0;
        }

        for (int i = 0; i < oneLen; i++) {
            caches[i][0] = twoChars[0] == oneChars[i] ? 1:0;
        }

        int maxLen = 0;
        int start = -1;
        for (int i = 1; i < oneLen; i++) {
            for (int j = 1; j < twoLen; j++) {
                if (oneChars[i] == twoChars[j]) {
                    caches[i][j] = caches[i - 1][j - 1] + 1;
                }else {
                    caches[i][j] = 0;
                }
                if (maxLen < caches[i][j]) {
                    maxLen = caches[i][j];
                    start = i - maxLen + 1;
                }
//                maxLen = Math.max(maxLen,caches[i][j]);
            }
        }

        return start == -1 ? null:one.substring(start,start+maxLen);
    }

    public static int maxSuArr01(String one,String two) {

        if (one == null || one.length() == 0
                || two == null || two.length() == 0) {
            return 0;
        }

        int oneLen = one.length();
        int twoLen = two.length();

        char[] oneChars = one.toCharArray();
        char[] twoChars = two.toCharArray();

        int idxRow = 0;
        int idxCol = oneLen - 1;
        int maxLen = 0;
        while (idxRow < oneLen) {
            int startX = idxRow;
            int startY = idxCol;
            int preValue = 0;
            while (startX < oneLen && startY < twoLen) {
                if (oneChars[startX] == twoChars[startY]) {
                    preValue = preValue + 1;
                }else {
                    preValue = 0;
                }
                maxLen = Math.max(preValue,maxLen);
                startX++;
                startY++;
            }

            if (idxCol > 0) {
                idxCol--;
            }else {
                idxRow++;
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        String one = "abfgk";
        String two = "cdbfghc";
//        int val = maxSubArr(one, two);
//        System.out.println(val);
//        String string = maxSubArr(one, two);
//        System.out.println(string);
        int maxed = maxSuArr01(one, two);
        System.out.println(maxed);
    }
}
